//给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。 
//
// 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。 
//
// 请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
//输出: [1,2],[1,4],[1,6]
//解释: 返回序列中的前 3 对数：
//     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
// 
//
// 示例 2: 
//
// 
//输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
//输出: [1,1],[1,1]
//解释: 返回序列中的前 2 对数：
//     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
// 
//
// 
//
// 提示: 
//
// 
// 1 <= nums1.length, nums2.length <= 10⁵ 
// -10⁹ <= nums1[i], nums2[i] <= 10⁹ 
// nums1 和 nums2 均为 升序排列 
// 
// 1 <= k <= 10⁴ 
// k <= nums1.length * nums2.length 
// 
//
// Related Topics 数组 堆（优先队列） 👍 644 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author ldltd
 * @date 2025-02-23 23:54:11
 * @description 373.查找和最小的 K 对数字
 */
public class FindKPairsWithSmallestSums{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindKPairsWithSmallestSums fun=new FindKPairsWithSmallestSums();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //超时
	public List<List<Integer>> kSmallestPairs1(int[] nums1, int[] nums2, int k) {
		PriorityQueue<List<Integer>> pq=new PriorityQueue<>((l1, l2)->l1.get(0)+l1.get(1)-l2.get(0)-l2.get(1));
		for (int i = 0; i < nums1.length; i++) {
			for (int j = 0; j < nums2.length; j++) {
				ArrayList<Integer> e = new ArrayList<>();
				e.add(nums1[i]);
				e.add(nums2[j]);
				pq.add(e);
			}
		}
		List<List<Integer>>res=new ArrayList<>();
		for (int i = 0; i < k; i++) {
			if(pq.isEmpty()) return res;
			res.add(pq.poll());
		}
		return res;
	}
	//不需要把所有对子都挑出来，只需要选符合条件的最小的对子就行了
	//假设当前已经选了n对最小的，则下一个n+1的最小的
	//一定在(ai+1,bi),(ai,bi+1)中
	//待选的对子中，选择最小的一个
	//可以先把nums1的前k个索引加入，(0,0),(1,0),(2,0),……(k-1,0)
	//每次从队列取对子时，只需要改变num2的索引，这样可以避免重复加入元素
	public List<List<Integer>> kSmallestPairs2(int[] nums1, int[] nums2, int k) {
		PriorityQueue<int[]> pq = new PriorityQueue<>(k, (o1, o2)->{
			return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]];
		});
		List<List<Integer>> ans = new ArrayList<>();
		int m = nums1.length;
		int n = nums2.length;
		for (int i = 0; i < Math.min(m, k); i++) {
			pq.offer(new int[]{i,0});
		}
		while (k-- > 0 && !pq.isEmpty()) {
			int[] idxPair = pq.poll();
			List<Integer> list = new ArrayList<>();
			list.add(nums1[idxPair[0]]);
			list.add(nums2[idxPair[1]]);
			ans.add(list);
			if (idxPair[1] + 1 < n) {
				pq.offer(new int[]{idxPair[0], idxPair[1] + 1});
			}
		}

		return ans;

	}
	//二分，先找到第k小的数对和为p，然后计算小于目标k的数有多少对
	//找到最小的k满足小于等于他的数对刚好大于等于p
	//
	public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
		int m = nums1.length;
		int n = nums2.length;

		/*二分查找第 k 小的数对和的大小*/
		int left = nums1[0] + nums2[0];
		int right = nums1[m - 1] + nums2[n - 1];
		int pairSum = right;
		while (left <= right) {
			int mid = left + ((right - left) >> 1);
			long cnt = 0;
			int start = 0;
			int end = n - 1;
			while (start < m && end >= 0) {
				if (nums1[start] + nums2[end] > mid) {
					end--;
				} else {
					cnt += end + 1;
					start++;
				}
			}
			if (cnt < k) {
				left = mid + 1;
			} else {
				pairSum = mid;
				right = mid - 1;
			}
		}

		List<List<Integer>> ans = new ArrayList<>();
		int pos = n - 1;
		/*找到小于目标值 pairSum 的数对*/
		for (int i = 0; i < m; i++) {
			while (pos >= 0 && nums1[i] + nums2[pos] >= pairSum) {
				pos--;
			}
			for (int j = 0; j <= pos && k > 0; j++, k--) {
				List<Integer> list = new ArrayList<>();
				list.add(nums1[i]);
				list.add(nums2[j]);
				ans.add(list);
			}
		}

		/*找到等于目标值 pairSum 的数对*/
		pos = n - 1;
		for (int i = 0; i < m && k > 0; i++) {
			int start1 = i;
			while (i < m - 1 && nums1[i] == nums1[i + 1]) {
				i++;
			}
			while (pos >= 0 && nums1[i] + nums2[pos] > pairSum) {
				pos--;
			}
			int start2 = pos;
			while (pos > 0 && nums2[pos] == nums2[pos - 1]) {
				pos--;
			}
			if (nums1[i] + nums2[pos] != pairSum) {
				continue;
			}
			int count = (int) Math.min(k, (long) (i - start1 + 1) * (start2 - pos + 1));
			for (int j = 0; j < count && k > 0; j++, k--) {
				List<Integer> list = new ArrayList<>();
				list.add(nums1[i]);
				list.add(nums2[pos]);
				ans.add(list);
			}
		}
		return ans;
	}



}
//leetcode submit region end(Prohibit modification and deletion)

}
